\documentclass[E:/GsjzTle/main/main.tex]{subfiles}

\begin{document}

\hypertarget{header-n0}{%
\subsection{题目大意}\label{header-n0}}

\begin{quote}
给定一个长度为 \(N\) 的序列 \(A\)\\
有 \(Q\) 次操作，每次操作给定两个数 \(i\) , \(X\)，使得
\(A[i] = A[i] \times X\) \\
问每次操作后整个序列的 \(gcd\) 为多少 （对 \(1e9+7\) 取模）
\end{quote}

\hypertarget{header-n4}{%
\subsection{解题思路}\label{header-n4}}

\begin{quote}
显然 \(gcd\) 不满足同余定理 ( \(gcd(4,6) \% 3\) \(!=\)
\(gcd(4\%3,6)\%3\) )\\
而 \(A[i]\) 和 \(X\) 最大值都不超过 \(2e5\) ， 所以可考虑质因子分解\\
首先要知道对于一个数它的质因子个数是 \(log\) 级别的\\
有个贪心的证明方法

\begin{quote}
要让一个数的质因子最多，那这个数的质因子就应该尽可能小\\
那么就让他的质因子为 \(2,3,5,7,11,13,...\)\\
那么它就等于 \(2 × 3 × 5 × 7 × 11 × 13 ×...\) \\
当乘到 \(29\) 时，它已经大于 \(6e9\) 了，所以一个数的质因子个数是
\(log\) 级别的
\end{quote}

于是可以用 \(map\) 开个二维动态数组 \(f[i][j]\)，\(f[i][j]\) 表示
\(a[i]\) 的质因子 \(j\) 的幂次\\
这样使用的空间最多为 \((N + Q) × log\)\\
对于一个质数 \(P\) ，它对答案产生贡献的条件是： \(A[1] \)
\textasciitilde{} \(A[N]\) 的质因子都包含 \(P\)\\
也就是 \(P\) 作为质因子一共出现了 \(N\)
次，而它的贡献显然是出现过的最小幂次\\
于是可以对每个质数 \(p\) 开个 \(set\) \\
当 \(A[i]\) 的质因子包含 \(p\) 时，往 \(set[p]\) 里插入对应的幂次\\
而当 \(set[p].size() =n\) 时，\(p\) 就会对答案产生
\(p^{set[p].begin() - pre[p]}\) 贡献 \\
其中 \(pre[p]\) 表示上一次 \(p\) 对答案产生的贡献，其初始值为 \(0\)
\end{quote}

\begin{lstlisting}
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll pow_mod(ll x,ll n,ll mod)
{
	ll res = 1;
	while(n)
	{
		if(n & 1) res = res * x % mod;
		x = x * x % mod;
		n >>= 1;
	}
	return res;
}
int prime[200010] , minprime[200010];
int euler(int n)
{
	int c = 0 , i , j;
	for(i = 2 ; i <= n ; i ++)
	{
		if(!minprime[i]) prime[++ c] = i , minprime[i] = i;
		for(j = 1 ; j <= c && i * prime[j] <= n ; j ++)
		{
			minprime[i * prime[j]] = prime[j];
			if(i % prime[j] == 0) break ;
		}
	}
	return c;
}
const ll mod = 1e9 + 7;
const int N = 3e5 + 10;
int n , q , I , X , a[N] , pre[N];
map<int , int>f[N];
multiset<int>se[N];
signed main()
{	
	ios::sync_with_stdio(false);
	cin.tie(0) , cout.tie(0);
	int sum = euler(200000);
	ll gcdd = 1;
	cin >> n >> q;
	for(int i = 1 ; i <= n ; i ++) cin >> a[i];
	for(int i = 1 ; i <= n ; i ++)
	{
		for(int j = 2 ; j * j <= a[i] ; j ++) if(a[i] % j == 0)
		{
			int c = 0;
			while(a[i] % j == 0) a[i] /= j , c ++ ;
			f[i][j] = c;
			se[j].insert(c);
		}
		if(a[i] > 1) f[i][a[i]] = 1 , se[a[i]].insert(1);
	}
	for(int i = 1 ; i <= sum ; i ++)
	{
		int p = prime[i];
		if(se[p].size() == n)
		{
			auto j = *se[p].begin();
			gcdd = gcdd * pow_mod(1LL * p , 1LL * j , mod) % mod;
			pre[p] = j;
		}
	}
	while(q --)
	{
		cin >> I >> X;
		for(int j = 1 ; prime[j] * prime[j] <= X && j <= sum ; j ++) if(X % prime[j] == 0)
		{
			int c = 0 , p = prime[j];
			while(X % p == 0) X /= p , c ++ ;
			if(f[I].count(p))
			{
				auto it = se[p].find(f[I][p]);
				se[p].erase(it);
			}
			f[I][p] += c;
			se[p].insert(f[I][p]);
			if(se[p].size() == n)
			{
				auto it = *se[p].begin();
				gcdd = gcdd * pow_mod(p , it - pre[p] , mod) % mod;
				pre[p] = it;
			}
		}
		if(X > 1)
		{
			if(f[I].count(X))
			{
				auto it = se[X].find(f[I][X]);
				se[X].erase(it);
			}		
			f[I][X] += 1;
			se[X].insert(f[I][X]);
			if(se[X].size() == n)
			{
				auto it = *se[X].begin();
				gcdd = gcdd * pow_mod(X , it - pre[X] , mod) % mod;
				pre[X] = it;
			}
		}
		cout << gcdd << '\n';
	}
	return 0;
}
\end{lstlisting}

\end{document}
